|
Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity estimates involve the number of buckets. Bucket sort works as follows: # Set up an array of initially empty "buckets". # Scatter: Go over the original array, putting each object in its bucket. # Sort each non-empty bucket. # Gather: Visit the buckets in order and put all elements back into the original array. ==Pseudocode== function bucketSort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert ''array()'' into buckets for i = 0 to n - 1 do nextSort(buckets()); return the concatenation of buckets(), ...., buckets() Here ''array'' is the array to be sorted and ''n'' is the number of buckets to use. The function ''msbits(x,k)'' returns the ''k'' most significant bits of ''x'' (''floor(x/2^(size(x)-k))''); different functions can be used to translate the range of elements in ''array'' to ''n'' buckets, such as translating the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. The function ''nextSort'' is a sorting function; using ''bucketSort'' itself as ''nextSort'' produces a relative of radix sort; in particular, the case ''n = 2'' corresponds to quicksort (although potentially with poor pivot choices). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bucket sort」の詳細全文を読む スポンサード リンク
|